/* 递归解法 */
var inorderTraversal = function (root) {
  let ans = []
  if (root === null) {
    return ans
  }
  if (root.left) ans = inorderTraversal(root.left)
  ans = [...ans, root.val]
  if (root.right) ans = ans.concat(inorderTraversal(root.right))
  return ans
}

inorderTraversal = function (root) {
  let stack = []
  let ans = []
  let p = root
  while (p || stack.length) {
    if (p !== null) {
      stack.push(p)
      p = p.left
    } else {
      p = stack.pop()
      ans.push(p.val)
      p = p.right
    }
  }
  return ans
  // let p = root
  // let stack = []
  // let ans = []
  // if (p) {
  //   stack.push(root)
  //   while (p || stack.length > 0) {
  //     while (p.left) {
  //       stack.push(p.left)
  //       p = p.left
  //     }
  //     while (stack.length > 0) {
  //       p = stack.pop()
  //       ans.push(p.val)
  //       if (p.right) {
  //         p = p.right
  //         break
  //       }
  //     }
  //   }
  // }
  // return ans
}


/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let ans = []
  let cur = root
  while (cur) {
    if (cur.left) {
      let mr = cur.left
      while (mr.right != null && mr.right != cur) {
        mr = mr.right
      }

      if (mr.right == null) {
        mr.right = cur
        cur = cur.left
      } else if (mr.right == cur) {
        ans.push(cur.val)
        mr.right = null
        cur = cur.right
      }
    } else {
      ans.push(cur.val)
      cur = cur.right
    }
  }


  return ans
};